SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Graph kernel</title>

</head>

Graph kernel

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">This article is about machine learning. For the graph-theoretical notion, see <a href="Glossary_of_graph_theory" title="Glossary of graph theory">Glossary of graph theory</a>.</div>

In <a href="Structure_mining" title="Structure mining">structure mining</a>, a graph kernel is a <a href="Positive-definite_kernel" title="Positive-definite kernel">kernel function</a> that computes an <a href="Inner_product_space" title="Inner product space">inner product</a> on <a href="Graph_(abstract_data_type)" title="Graph (abstract data type)">graphs</a>.<a href="#cite_note-Vishwanathan-1">[1]</a>

Graph kernels can be intuitively understood as functions measuring the similarity of pairs of graphs. They allow <a href="Kernel_trick" class="mw-redirect" title="Kernel trick">kernelized</a> learning algorithms such as <a href="Support_vector_machine" title="Support vector machine">support vector machines</a> to work directly on graphs, without having to do <a href="Feature_extraction" class="mw-redirect" title="Feature extraction">feature extraction</a> to transform them to fixed-length, real-valued <a href="Feature_vector" class="mw-redirect" title="Feature vector">feature vectors</a>. They find applications in <a href="Bioinformatics" title="Bioinformatics">bioinformatics</a>, in <a href="Chemoinformatics" class="mw-redirect" title="Chemoinformatics">chemoinformatics</a> (as a type of <a href="Molecule_kernel" class="mw-redirect" title="Molecule kernel">molecule kernels</a><a href="#cite_note-Ralaivola2005-2">[2]</a>), and in <a href="Social_network_analysis" title="Social network analysis">social network analysis</a>.<a href="#cite_note-Vishwanathan-1">[1]</a>

Concepts of graph kernels have been around since the 1999, when D. Haussler<a href="#cite_note-3">[3]</a> introduced convolutional kernels on discrete structures. The term graph kernels was more officially coined in 2002 by R. I. Kondor and <a href="John_D._Lafferty" title="John D. Lafferty">J. Lafferty</a><a href="#cite_note-4">[4]</a>

as kernels on graphs, i.e. similarity functions between the nodes of a single graph, with the <a href="World_Wide_Web" title="World Wide Web">World Wide Web</a> <a href="Hyperlink" title="Hyperlink">hyperlink</a> graph as a suggested application. In 2003, Gärtner et al.<a href="#cite_note-Gaertner-5">[5]</a>

and Kashima et al.<a href="#cite_note-Kashima-6">[6]</a>

defined kernels between graphs. In 2010, Vishwanathan et al. gave their unified framework.<a href="#cite_note-Vishwanathan-1">[1]</a> In 2018, Ghosh et al. <a href="#cite_note-7">[7]</a> described the history of graph kernels and their evolution over two decades.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

The marginalized graph kernel has been shown to allow accurate predictions of the atomization energy of small organic molecules.<a href="#cite_note-8">[8]</a>

<div class="mw-heading mw-heading2"><h2 id="Example_Kernels">Example Kernels</h2></div>

An example of a kernel between graphs is the random walk kernel,<a href="#cite_note-Gaertner-5">[5]</a><a href="#cite_note-Kashima-6">[6]</a> which conceptually performs <a href="Random_walk" title="Random walk">random walks</a> on two graphs simultaneously, then counts the number of <a href="Path_(graph_theory)" title="Path (graph theory)">paths</a> that were produced by both walks. This is equivalent to doing random walks on the <a href="Tensor_product_of_graphs" title="Tensor product of graphs">direct product</a> of the pair of graphs, and from this, a kernel can be derived that can be efficiently computed.<a href="#cite_note-Vishwanathan-1">[1]</a>

Another examples is the Weisfeiler-Leman graph kernel<a href="#cite_note-9">[9]</a> which computes multiple rounds of the <a href="Weisfeiler-Leman_algorithm" class="mw-redirect" title="Weisfeiler-Leman algorithm">Weisfeiler-Leman algorithm</a> and then computes the similarity of two graphs as the inner product of the histogram vectors of both graphs. In those histogram vectors the kernel collects the number of times a color occurs in the graph in every iteration.

Note that the Weisfeiler-Leman kernel in theory has an infinite dimension as the number of possible colors assigned by the Weisfeiler-Leman algorithm is infinite. By restricting to the colors that occur in both graphs, the computation is still feasible.

<ul><li><a href="Tree_kernel" title="Tree kernel">Tree kernel</a>, as special case of non-cyclic graphs</li>

<li><a href="Molecule_mining" title="Molecule mining">Molecule mining</a>, as special case of small multi-label graphs</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFS.V._N._VishwanathanNicol_N._SchraudolphRisi_KondorKarsten_M._Borgwardt2010" class="citation journal cs1">S.V. N. Vishwanathan; Nicol N. Schraudolph; Risi Kondor; <a href="Karsten_Borgwardt" title="Karsten Borgwardt">Karsten M. Borgwardt</a> (2010). <a rel="nofollow" class="external text" href="http://jmlr.csail.mit.edu/papers/volume11/vishwanathan10a/vishwanathan10a.pdf">"Graph kernels"</a> (PDF). <a href="Journal_of_Machine_Learning_Research" title="Journal of Machine Learning Research">Journal of Machine Learning Research</a>. 11: 1201–1242.</cite>

</li>

<li id="cite_note-Ralaivola2005-2"><a href="#cite_ref-Ralaivola2005_2-0">^</a> <cite id="CITEREFL._RalaivolaS._J._SwamidassH._SaigoP._Baldi2005" class="citation journal cs1">L. Ralaivola; S. J. Swamidass; H. Saigo; P. Baldi (2005). "Graph kernels for chemical informatics". Neural Networks. 18 (8): 1093–1110. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.neunet.2005.07.009">10.1016/j.neunet.2005.07.009</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/16157471">16157471</a>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFHaussler1999" class="citation book cs1">Haussler, David (1999). Convolution Kernels on Discrete Structures. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.110.638">10.1.1.110.638</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFRisi_Imre_KondorJohn_Lafferty2002" class="citation conference cs1">Risi Imre Kondor; John Lafferty (2002). <a rel="nofollow" class="external text" href="http://people.cs.uchicago.edu/~risi/papers/diffusion-kernels.pdf">Diffusion Kernels on Graphs and Other Discrete Input Spaces</a> (PDF). Proc. Int'l Conf. on Machine Learning (ICML).</cite>

</li>

<li id="cite_note-Gaertner-5">^ <a href="#cite_ref-Gaertner_5-0">a</a> <a href="#cite_ref-Gaertner_5-1">b</a> <cite id="CITEREFThomas_GärtnerPeter_A._FlachStefan_Wrobel2003" class="citation conference cs1">Thomas Gärtner; Peter A. Flach; Stefan Wrobel (2003). On graph kernels: Hardness results and efficient alternatives. Proc. the 16th Annual Conference on Computational Learning Theory (COLT) and the 7th Kernel Workshop. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-45167-9_11">10.1007/978-3-540-45167-9_11</a>.</cite>

</li>

<li id="cite_note-Kashima-6">^ <a href="#cite_ref-Kashima_6-0">a</a> <a href="#cite_ref-Kashima_6-1">b</a> <cite id="CITEREFHisashi_KashimaKoji_TsudaAkihiro_Inokuchi2003" class="citation conference cs1">Hisashi Kashima; Koji Tsuda; Akihiro Inokuchi (2003). <a rel="nofollow" class="external text" href="http://www.aaai.org/Papers/ICML/2003/ICML03-044.pdf">Marginalized kernels between labeled graphs</a> (PDF). Proc. the 20th International Conference on Machine Learning (ICML).</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFGhoshDasGonçalvesQuaresma2018" class="citation journal cs1">Ghosh, Swarnendu; Das, Nibaran; Gonçalves, Teresa; Quaresma, Paulo; Kundu, Mahantapas (2018). "The journey of graph kernels through two decades". Computer Science Review. 27: 88–111. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.cosrev.2017.11.002">10.1016/j.cosrev.2017.11.002</a>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFYu-Hang_TangWibe_A._de_Jong2019" class="citation journal cs1">Yu-Hang Tang; Wibe A. de Jong (2019). "Prediction of atomization energy using graph kernel and active learning". The Journal of Chemical Physics. 150 (4): 044107. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1810.07310">1810.07310</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2019JChPh.150d4107T">2019JChPh.150d4107T</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1063%2F1.5078640">10.1063/1.5078640</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/30709286">30709286</a>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> Shervashidze, Nino, et al. "Weisfeiler-lehman graph kernels." Journal of Machine Learning Research 12.9 (2011).

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox-body{font-style:italic}.mw-parser-output .asbox-note{font-size:smaller}.mw-parser-output .asbox .navbar{position:absolute;top:-0.75em;right:1em;display:none}.mw-parser-output :not(p):not(.asbox)+style+.asbox,.mw-parser-output :not(p):not(.asbox)+link+.asbox{margin-top:3em}

/* end https://en.wikipedia.org/ */

</style>

</div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-31" href="https://en.wikipedia.org/wiki/?title=Graph_kernel&oldid=1303510078">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>